#include "test_for_singly_linked_list.h"
#include <stdlib.h>
#include <assert.h>
#include <math.h>

/**
 * 因为用例代表的数字太大，用我的计算方法无法处理。浮点数丢失精度，
 */
const char* test_case1 = "[5,6,4]";
const char* test_case2 = "[1,2,1,3,2,100]";

Node* create()
{
    Node* head = NULL;
    head = (Node*)malloc(sizeof(Node));
    if(head == NULL)
    {
        printf("malloc failed!\r\n");
        return NULL; 
    }
    head->data = 0;            //数据域赋初始值
    head->next = NULL;         //指针域赋初始值

    return head;
}

// void head(Node* head, int num)
// {
//     Node* p, pr;
//     p = head->next; // p  为头结点的下一个
//     pr = NULL;      // pr 为新插入的结点 插在 head 后 p 前
//     pr = (Node*)malloc(sizeof(Node));

//     if (pr == NULL)
//     {
//         printf("malloc failed!\r\n");
//         return;
//     }

//     pr->data = num; // 给pr数据域赋值

//     pr->next = head; // 头插
//     head = pr;
// }

void head(Node** head, int num)
{
    Node* pr = NULL;

    pr = create();
    pr->data = num; // 给pr数据域赋值

    pr->next = *head;
    *head = pr;
}

SList *buynode(SLData x)
{
    SList *newnode = (SList *)calloc(1, sizeof(SList)); // 尽量用calloc，该函数可以将申请的空间初
                                                        //  始化为0
    assert(newnode); // 检测创建是否成功

    newnode->a = x;
    return newnode;
}

void SL_Front_stick(SList **phead, SLData x) // 头插
{
    assert(*phead);

    SList *pTemp = buynode(x);

    pTemp->next = *phead; // 让新结点指向原本的头节点
    *phead = pTemp;       // 让原本头结点指针指向新节点
}


void print(SList* phead)
{
    while (phead)
    {
        printf("%d->", phead->a);
        phead = phead->next;
    }
    printf("null\n");
}

void test_for_singly_linked_list(void)
{
    Node* pList = create();
    SList* pList_x = buynode(10);

    printf("test for singly linked list:\r\n");

    pList->data = 8;
    head(&pList, 9);

    printf(LIGHT_CYAN "addr of pList is %p\r\n" NONE, &pList);
    printf(LIGHT_CYAN "addr of next is %p\r\n" NONE, pList->next);

    memory_dump(pList, 16, pList, pList);

    memory_dump(pList->next, 16, pList->next, pList->next);

    head(&pList, 10);
    printf(LIGHT_PURPLE "addr of pList is %p\r\n" NONE, &pList);
    printf(LIGHT_PURPLE "data of pList is %d\r\n" NONE, pList->next->data);

    printf(YELLOW "addr of pList is %p\r\n" NONE, &pList_x);
    printf(YELLOW "value of pList_x is %d\r\n" NONE, pList_x->a);
    SL_Front_stick(&pList_x, 12);
    printf(YELLOW "addr of pList is %p\r\n" NONE, &pList_x);
    printf(YELLOW "value of pList_x is %d\r\n" NONE, pList_x->a);
    print(pList_x);

    while (pList)
    {
        printf("%d->", pList->data);
        pList = pList->next;
    }

    struct ListNode* ptest_node = test_case_create((char* )test_case1);
    print_node(ptest_node);
    
    struct ListNode* ptest_node1 = test_case_create((char* )test_case2);
    print_node(ptest_node1);

    struct ListNode* ptest_node2 = addTwoNumbers(ptest_node, ptest_node1);
    print_node(ptest_node2);

    struct ListNode* ptest_node3 = mergeTwoLists(ptest_node, ptest_node1);
    print_node(ptest_node3); //打印测试的原始数据

    printf(LIGHT_PURPLE "step1 del tail node: \n" NONE); // STEP - 1 删除尾节点
    tail_delete(&ptest_node3);
    print_node(ptest_node3);

    stick_node(&ptest_node3, 1, 1010); // STEP - 2 在位置 1 插入一个节点
    print_node(ptest_node3);

    printf(LIGHT_PURPLE "step 3 del head node: \n" NONE);
    delete_node(&ptest_node3, 0); // STEP - 3 删除位置 0 的节点，类似于删除头结点
    print_node(ptest_node3);

    printf(LIGHT_PURPLE "step 4 del node 3: \n" NONE);
    delete_node(&ptest_node3, 3); // STEP - 4 删除位置 3 的节点
    print_node(ptest_node3);

    printf(LIGHT_PURPLE "step 5 revise node 4: \n" NONE);
    revise_node(&ptest_node3, 4, 1024); // STEP - 5 修改位置 4 的值为 1024
    print_node(ptest_node3);

    destroy_node(&ptest_node3); // STEP - END 摧毁此链表
    print_node(ptest_node3);

    free(pList);

    struct ListNode* ptest_head_del = NULL;
    ptest_head_del = create_node(2048);
    printf(LIGHT_PURPLE "step 6 test just one node head del: \n" NONE);
    head_delete(&ptest_head_del); // STEP - 6 头删只有一个节点的单向链表
    print_node(ptest_head_del);
}

/* 从 CSDN 上学习单向链表时，对上面的代码验证与修改，自我备份 */

struct ListNode* create_node(unsigned int node_val)
{
    struct ListNode* pnode = NULL;
    pnode = (struct ListNode* )malloc(sizeof(struct ListNode));
    assert(pnode);
    pnode->val = node_val;
    pnode->next = NULL;
    return pnode;
}

void destroy_node(struct ListNode** phead)
{
    if(phead != NULL && *phead != NULL)
    {
        struct ListNode *cur = *phead; // 指向头节点
        struct ListNode *prev = NULL;  // 指向cur上一个节点
        while (cur)
        {
            prev = cur;      // 记录上一个节点地址
            cur = cur->next; // 移至下一个节点
            free(prev);      // 释放节点
        }
        *phead = NULL;
    }
}

void head_insert(struct ListNode** head_node, unsigned int node_val)
{
    struct ListNode* pnode = NULL;
    pnode = create_node(node_val);
    pnode->next = *head_node;
    *head_node = pnode;
}

/**
 * @brief 删除头节点
 * @param phead 传入头节点的地址
 * @return NONE
 */
void head_delete(struct ListNode** phead)
{
    if(phead != NULL && *phead != NULL)
    {
        struct ListNode *cur = *phead;
        *phead = (*phead)->next;
        free(cur);
    }
}

void tail_insert(struct ListNode** head_node, unsigned int node_val)
{
    if((head_node != NULL) && (*head_node != NULL))
    {
        struct ListNode* pnode = create_node(node_val);
        struct ListNode* ptemp_node = *head_node;
        while(ptemp_node->next != NULL) //尾节点的下一个节点为 NULL
        {
            ptemp_node = ptemp_node->next;
        }
        ptemp_node->next = pnode;
    }
}

/**
 * @brief 删除尾节点
 * @param phead 头节点的地址
 * @return NONE
 */
void tail_delete(struct ListNode** phead)
{
    if(phead != NULL && *phead != NULL)
    {
        struct ListNode *cur = *phead;
        struct ListNode *prev = NULL;
        while (cur->next) // 让指针停留在最后一个结点
        {
            prev = cur; // 记录cur前一个结点
            cur = cur->next;
        }
        prev->next = NULL;
        free(cur);
    }
}

/**
 * @brief 从指定位置插入节点，所有节点的序号从 0 开始。
 * @param phead 头节点地址 
 * @param pos_add 指定的插入位置，从 0 开始。
 * @param node_val 指定位置插入的节点的数据内容
 * @return NONE
 */
void stick_node(struct ListNode** phead, unsigned int pos_add, unsigned int node_val)
{
    if((phead != NULL) && (*phead != NULL))
    {
        if (pos_add == 0) // 如果位置为 0 ，则头插
        {
            head_insert(phead, node_val);
        }
        else
        {
            struct ListNode* newnode = create_node(node_val);
            struct ListNode* cur = *phead;
            struct ListNode* prev = NULL;
            while (pos_add-- && (cur != NULL)) //如果 pos_add 超出链表节点总数，则尾插
            {
                prev = cur;
                cur = cur->next;
            }
            prev->next = newnode;
            if(cur != NULL)
            {
                newnode->next = cur;
            }
        }
    }
}

/**
 * @brief 删除指定位置的节点，所有节点的序号从 0 开始。
 * @param phead 头节点地址 
 * @param pos_del 指定的删除的位置，从 0 开始。
 * @return NONE
 */
void delete_node(struct ListNode** phead, unsigned pos_del)
{
    if(phead != NULL && *phead != NULL)
    {
        struct ListNode *cur = *phead;
        struct ListNode *prev = NULL;
        if (pos_del == 0)
        {
            head_delete(phead);
        }
        else
        {
            while (pos_del-- && (cur->next != NULL)) //如果 pos_del 超出链表节点总数，则尾删
            {
                prev = cur;
                cur = cur->next;
            }
            prev->next = cur->next;
            free(cur);
        }
    }
}

void revise_node(struct ListNode** phead, unsigned int pos, unsigned int node_val)
{
    if(phead != NULL && *phead != NULL)
    {
        struct ListNode *cur = *phead;
        while (pos-- && (cur != NULL))
        {
            cur = cur->next;
        }
        if(cur != NULL)
        {
            cur->val = node_val;
        }
    }
}

void print_node(struct ListNode* node)
{
    printf(GREEN "[" NONE);
    while(node)
    {
        printf(GREEN "%d" NONE, node->val);
        node = node->next;
        if(node != NULL)
        {
            printf(GREEN "," NONE, node->val);
        }
    }
    printf(GREEN "]\r\n" NONE);
}

/* 对 leetcode 上的练习题，自我的解决方法，非最优解，有的无法通过全部测试用例 */

struct ListNode* test_case_create(char* src)
{
    struct ListNode* pnode = NULL;
    unsigned int current_digit = 0;
    while(*src != '\0')
    {
        if(*src == ',' || *src == ']')
        {
            src--;
            current_digit = *src - '0';
            src++;
            if(pnode == NULL)
            {
                pnode = create_node(current_digit);
            }
            else
            {
                tail_insert(&pnode, current_digit);
            }
        }
        src++;
    }
    return pnode;
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
{
    long double l1_num = 0, l2_num = 0, sum = 0, the_mod = 0;
    long double index = 1; //节点中整数代表的位置
    struct ListNode* ret_node = create_node(0); //创建头节点
    while(l1)
    {
        l1_num += l1->val * index;
        l1 = l1->next;
        index *= 10;
    }
    index = 1;
    while(l2)
    {
        l2_num += l2->val * index;
        l2 = l2->next;
        index *= 10;
    }
    sum = l1_num + l2_num;

    ret_node->val = fmod(sum,10); //头结点存和的个位
    sum /= 10;
    while(sum >= 1)
    {
        the_mod = fmod(sum, 10);
        tail_insert(&ret_node, (unsigned int)the_mod);
        sum /= 10;
    }
    return ret_node;
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    int min_value = 0;
    while(list2) //将链表 2 的所有数据全部插入到链表 1 的尾部。
    {
        tail_insert(&list1, list2->val);
        list2 = list2->next;
    }
    struct ListNode* pnew_node = create_node(list1->val);
    struct ListNode* pret_node = create_node(list1->val);
    pnew_node = list1;pnew_node->next = list1->next;
    pret_node = list1;pret_node->next = list1->next;

    while(pret_node)
    {
        min_value = pnew_node->val;
        while(pnew_node)
        {
            if(pnew_node->val < min_value)
            {
                int temp = min_value;
                min_value = pnew_node->val;
                pnew_node->val = temp;
            }
            pnew_node = pnew_node->next;
        }
        pret_node->val = min_value;
        pret_node = pret_node->next;
        if(pret_node != NULL)
        {
            pnew_node = pret_node; //切换到下一个节点
            pnew_node->next = pret_node->next;
        }
    }
    return list1;
}
